trait SimpleInput { self: SimpleInput with SimpleResults =>
  // The type of the elements consumed by this parser
  type Elem
  type Input
  implicit def InputIsParseInput(in: Input): ParseInput
  trait ParseInput {
  	def first: Elem
    def rest: Input

  	def result[T](r: T): Success[T]
    def failure: Failure
    def error: Error
  }
}

trait SimpleResults { self: SimpleInput with SimpleResults =>
  trait Result[+T] {
    def next: Input

    def map[U](f: T => U): Result[U]
    def flatMap[U](f: T => Result[U]): Result[U]
    def flatMapWithNext[U](f: T => Input => Result[U]): Result[U]
    def filter(f: T => Boolean): Result[T]
    def append[U >: T](alt: => Result[U]): Result[U]
    
    def explain(ei: String): Result[T]
    def toError: Error
  }

  case class Success[+T](result: T, next: Input)(val zero: Result[Nothing]) extends Result[T] {
    def map[U](f: T => U)                              = Success(f(result), next)(zero)
    def flatMap[U](f: T => Result[U])                  = f(result)   
    def flatMapWithNext[U](f: T => Input => Result[U]) = f(result)(next)    
    def filter(f: T => Boolean): Result[T]             = if(f(result)) this else zero
    def append[U >: T](alt: => Result[U])              = this
    
    def explain(ei: String) =  this
    def toError: Error = Error("unknown error", next)    
  }

  case class Failure(errMsg: String, next: Input) extends Result[Nothing] {
    def map[U](f: Nothing => U)                        = this
    def flatMap[U](f: Nothing => Result[U])            = this
    def flatMapWithNext[U](f: Nothing => Input => Result[U]) = this
    def filter(f: Nothing => Boolean): Result[Nothing] = this
    def append[U](alt: => Result[U])                   = alt
    
    def explain(ei: String) = Failure(ei, next)
    def toError: Error = Error(errMsg, next)
  }
  
  case class Error(errMsg: String, next: Input) extends Result[Nothing] {
    def map[U](f: Nothing => U)                        = this
    def flatMap[U](f: Nothing => Result[U])            = this
    def flatMapWithNext[U](f: Nothing => Input => Result[U]) = this
    def filter(f: Nothing => Boolean): Result[Nothing] = this
    def append[U](alt: => Result[U])                   = this
    
    def explain(ei: String) = Error(ei, next)
    def toError: Error = this
  }  
}

trait SimpleParsers extends SimpleResults {
  def Parser[T](f: Input => Result[T]) 
    = new Parser[T]{ def apply(in: Input) = f(in) }

  abstract class Parser[+T] extends (Input => Result[T]) { 
    def flatMap[U](f: T => Parser[U]): Parser[U] 
      = Parser{in => this(in) flatMapWithNext(f)}

    def map[U](f: T => U): Parser[U] 
      = Parser{in => this(in) map(f)}

    def filter(f: T => Boolean): Parser[T]
      = Parser{in => this(in) filter(f)}
    
    def | [U >: T](p: => Parser[U]): Parser[U] 
      = Parser{in => Parser.this(in) append p(in)}
  
    def ~ [U](p: => Parser[U]): Parser[Pair[T, U]] 
      = for(a <- this; b <- p) yield (a,b)
      
    def ~> [U](p: => Parser[U]): Parser[U] = for(a <- this; b <- p) yield b
    def <~ [U](p: => Parser[U]): Parser[T] = for(a <- this; b <- p) yield a

    def ^^ [U](f: T => U): Parser[U] = map(f)
      
    def explainWith(msg: Input => String): Parser[T] = Parser{in =>
      this(in) explain msg(in)
    }
  
    def explain(msg: String): Parser[T] = Parser{in =>
      Parser.this(in) explain msg
    }

    def expected(kind: String): Parser[T] 
      = explainWith{in => ""+ kind +" expected, but \'"+ in.first +"\' found."}

    def dontBacktrack: Parser[T] = Parser{in => 
      this(in) match {
        case s@Success(x, n) => Success(x, n)(s.zero.toError)
        case ns => ns.toError
      }
    }

    def ~! [U](p: => Parser[U]): Parser[Pair[T, U]] 
      = dontBacktrack ~ p
  }  
  
  def consumeFirst: Parser[Elem] = Parser{in => 
    Success(in.first, in.rest)(Failure("unknown failure", in))
  }
  
  def acceptIf(p: Elem => Boolean): Parser[Elem] = consumeFirst filter(p)
  // = for(e <- consumeFirst; if p(e)) yield e
  implicit def accept(e: Elem): Parser[Elem] = acceptIf(_ == e).expected(e.toString)
  
}

trait MoreCombinators extends SimpleParsers {
  def success[T](v: T): Parser[T] = Parser{in => Success(v, in)(Failure("unknown failure", in))}
  
  def opt[T](p: => Parser[T]): Parser[Option[T]] 
    = ( p ^^ {x: T => Some(x)} 
      | success(None)
      )

  def rep[T](p: => Parser[T]): Parser[List[T]] 
    = rep1(p) | success(List())

  def rep1[T](p: => Parser[T]): Parser[List[T]] 
    = rep1(p, p)
  
  def rep1[T](first: => Parser[T], p: => Parser[T]): Parser[List[T]] 
    = first ~ rep(p) ^^ mkList

  def repsep[T, S](p: => Parser[T], q: => Parser[S]): Parser[List[T]]  
    = rep1sep(p, q) | success(List())
    
  def rep1sep[T, S](p: => Parser[T], q: => Parser[S]): Parser[List[T]]
    = rep1sep(p, p, q)
    
  def rep1sep[T, S](first: => Parser[T], p: => Parser[T], q: => Parser[S]): Parser[List[T]] 
    = first ~ rep(q ~> p) ^^ mkList
    
  def chainl1[T](p: => Parser[T], q: => Parser[(T, T) => T]): Parser[T] 
    = chainl1(p, p, q)
    
  def chainl1[T, U](first: => Parser[T], p: => Parser[U], q: => Parser[(T, U) => T]): Parser[T] 
    = first ~ rep(q ~ p) ^^ {
        case (x, xs) => xs.foldLeft(x){(_, _) match {case (a, (f, b)) => f(a, b)}}
      }

  def acceptSeq[ES <% Iterable[Elem]](es: ES): Parser[List[Elem]] 
    = es.foldRight[Parser[List[Elem]]](success(Nil)){(x, pxs) => (accept(x) ~ pxs) ^^ mkList}
  
  private def mkList[T] = (_ : Pair[T, List[T]]) match {case (x, xs) => x :: xs }
}

trait StringInput extends SimpleInput {
  type Input = String
  type Elem = Char
  private val EOI = 0.toChar

  class ParseInput(val self: Input)
  	def first: Elem = if(in == "") EOI else in(0)
  	def rest: Input = if(in == "") in else in.substring(1)
	}
  
  def eoi = accept(EOI)
}


// a program whose first argument must be "oxo", or "oxo oxo", or "oxo oxo oxo", ...
object OXOParser extends StringParsers {
  def oxo = 'o' ~ 'x' ~ 'o'
  def oxos: Parser[Any] = 
    ( oxo ~ ' ' ~ oxos
    | oxo
    )
  
  def main(args: Array[String]) = println((oxos ~ eoi)(args(0)))
}


object OXOParser2 extends StringParsers with MoreCombinators {
  def oxo  = acceptSeq("oxo") ^^ {x => x.mkString("")}
  def oxos = rep1sep(oxo, ' ')
  
  def main(args: Array[String]) = println((oxos <~ eoi)(args(0)))
}